#include "bignum.h"
#include <iomanip> //setw

#include <string> //string
#include <cstring> //strlen

using namespace std;

#define max(a, b) ((a)>(b) ?(a): (b))
int BigNum::value_cmp(vector<int> const &a, vector<int> const &b) {
    if(a.size()>b.size()) return 1;
    if(a.size()<b.size()) return -1;
    for(int i=a.size()-1; i>=0; i--) {
        if(a[i]>b[i]) return 1;
        if(a[i]<b[i]) return -1;
    }
    return 0;
}
BigNum::BigNum(int const opt) {
    unsigned x = opt;
    while (x){
        d.push_back(x%EBASE);
        x/=EBASE;
    }
}
BigNum::BigNum(char const *opt){
    int L=strlen(opt), b=0;
    while (opt[b]=='0') b++;
    while (L-b>=DLEN) {
        int x=0;
        for (int i=L-DLEN;i<L;i++) x=x*BASE+opt[i]-'0';
        d.push_back(x);
        L-=DLEN;
    }
    int x=0;
    for (int i=b;i<L;i++) x=x*BASE+opt[i]-'0';
    if(x)d.push_back(x);
    
}

void BigNum::clear(void){
    for (int i=0; i<d.size()-1;i++) {
        if (d[i]<0) {
            d[i]+=EBASE;
            d[i+1]--;
        }else if (d[i]>=EBASE) {
            d[i]-=EBASE;
            d[i+1]++;
        }
    }
    for (int i=d.size()-1; i>=0; i--)
        if (d[i]>0){
            d.resize(i+1);
            return;
        }
    d.resize(0);
}
istream& operator>>(istream &in,BigNum &opt){
    string str;
    in >> str;
    opt = BigNum(str.c_str());
    return in;
}
ostream& operator<<(ostream& out, BigNum const &opt){
    int i = opt.d.size();
    if(i==0) return out<<"0";
    out << opt.d[--i];
    while(i-- > 0) out << setw(DLEN) << setfill('0') << opt.d[i];
    return out;
}


bool BigNum::operator== (const BigNum &opt) const{
    return value_cmp(d, opt.d)==0;
}
bool BigNum::operator> (const BigNum &opt) const{
    return value_cmp(d, opt.d)>0;
}
bool BigNum::operator< (const BigNum &opt) const{
    return value_cmp(d, opt.d)<0;
}
bool BigNum::operator>= (const BigNum &opt) const{
    return value_cmp(d, opt.d)>=0;
}
bool BigNum::operator<= (const BigNum &opt) const{
    return value_cmp(d, opt.d)<=0;
}
BigNum &BigNum::operator+= (BigNum const &opt) {
    d.resize(max(opt.d.size(), d.size())+1, 0);
    for (int i=0; i<opt.d.size(); i++) d[i] += opt.d[i];
    clear();
    return *this;
}

BigNum &BigNum::operator-= (BigNum const &opt) {
    for (int i=opt.d.size()-1; i>=0; i--) d[i]-=opt.d[i];
    clear();
    return *this;
}
BigNum BigNum::operator* (const BigNum &opt) const {
    BigNum ret;
    ret.d.resize(d.size()+opt.d.size(), 0);
    int i, j, k;
    for(i=0; i<d.size(); i++) {
        for(j=0; j<opt.d.size(); j++)
            ret.d[i+j] += d[i]*opt.d[j];
        for(k=i; k<i+opt.d.size(); k++)
            if (ret.d[k]>=EBASE){
                ret.d[k+1] += ret.d[k]/EBASE;
                ret.d[k] %= EBASE;
            }
        while(ret.d[k]>=EBASE) { //ret.d[k]<=(EBASE+(EBASE-3))
            ret.d[k+1]++;
            ret.d[k++]-=EBASE;
        }
    }
    for (i=ret.d.size()-1; i>=0; i--)
        if (ret.d[i]>0) {
            ret.d.resize(i+1);
            return ret;
        }
    ret.d.resize(0);
    return ret;
}

BigNum BigNum::operator+ (BigNum const &b) const { 
    BigNum ret(*this);
    ret += b; 
    return ret;
}
BigNum BigNum::operator- (BigNum const &opt) const{
    BigNum ret(*this);
    ret -= opt;
    return ret;
}

BigNum BigNum::op_div_mod (const BigNum &opt, bool get_mod) const{
    BigNum div/* 商 */, mod/* 余数 */; 
    div.d.resize(d.size(), 0);
    mod.d = vector<int>(d.end()-min(d.size(), opt.d.size()-1), d.end());
    for (int j=d.size()-mod.d.size()-1; j>=0; j--) {
        mod.d.insert(mod.d.begin(), d[j]);
        while (mod >= opt) {
            div.d[j]++;
            mod -= opt;
        }
    }
    if(get_mod) return mod;
    div.clear();
    return div;
}
BigNum BigNum::operator++ (void){
    BigNum ret(*this);
    d[0]++;
    int slen = d.size()-1;
    int i;
    for (i=0; i<slen&&d[i]>=EBASE; i++) {
        d[i] -= EBASE;
        d[i+1]++;
    }
    if(i==slen && d[i]>=EBASE) {
        d[i] -= EBASE;
        d.push_back(1);
    }
    return ret;
}
BigNum BigNum::operator-- (void){
    BigNum ret(*this);
    d[0]--;
    int i;
    for (i=0; d[i]<0; i++) {
        d[i] += EBASE;
        d[i+1]--;
    }
    if(d[i]==0 && i==d.size()-1) d.resize(0);
    return ret;
}

BigNum &BigNum::operator+= (short const &opt) {
    d[0] += opt;
    clear();
    return *this;
}
BigNum &BigNum::operator-= (short const &opt) {
    d[0] -= opt;
    int i;
    for (i=0; d[i]<0; i++) {
        d[i] += EBASE;
        d[i+1]--;
    }
    if(d[i]==0 && i==d.size()-1) d.resize(0);
    return *this;
}
BigNum &BigNum::operator*= (short const &opt) { //opt < EBASE
    for (int i=0; i<d.size(); i++) d[i] *= opt;
    d.resize(d.size()+1, 0);
    for (int i=0; i<d.size(); i++)
        if (d[i] >= EBASE) {
            d[i+1] += d[i]/EBASE;
            d[i] %= EBASE;
        }
    for (int i=d.size()-1; i>=0; i--)
        if (d[i]>0){
            d.resize(i+1);
            return *this;
        }
    d.resize(0);
    return *this;
}

BigNum &BigNum::operator*= (BigNum const &b) {
    *this = *this * b;
    return *this;
}

BigNum &BigNum::operator/= (BigNum const &b) {
    *this = op_div_mod(b, false);
    return *this;
}


BigNum BigNum::operator^ (const int &opt) const{
    BigNum t, ret(1);
    if(opt==0)return ret;
    if(opt==1)return *this;
    int m=opt,i;
    while(m>1) {
        t = *this;
        for(i=2; i<=m; i<<=1)
           t=t*t;
        m -= i>>1;
        ret=ret*t;
    }
    if(m==1)ret=ret*(*this);
    return ret;
}

#ifdef BN_TEST
using std::cout;
using std::cin;
using std::endl;
int main(void) {
    BigNum a, b, c;
    cout << "a:"; cin >> a;
    cout << "b:"; cin >> b;
    cout << "a+b=" << a+b << endl;
    cout << "a-b=" << a-b << endl;
    cout << "a/b=" << a/b << endl;
    
    cout << "a%b=" << a%b << endl;
    cout << "a*b=" << (a*=b) << endl;
    c = BigNum(1); short const num = 12345;
    cout << "c*=12345:" << (c *= num) << endl; 
    cout << "c - 12345:" << (c - num) << endl; 
    cout << "c + 12345:" << (c + num) << endl; 
    return 0;
}

#endif //BN_TEST


